package com.wm.algorithm.array;

import com.wm.algorithm.linked.entity.ListNode;

import java.util.*;

/**
 * @ClassName: SimpleArray
 * @Description: 简单级别
 * @Author: WM
 * @Date: 2021-07-24 23:06
 **/
public class SimpleArray {

    /**
     * 121. 买卖股票的最佳时机
     * 方法2：动态规划+变量存储相邻状态
     * 思路：定义一个三维数组dp[n][k][m]，dp：最大的利润，其中n：天数；k：允许交易的最大次数；m：当前持有的状态，分为两种
     * 1表示持有，0表示没有持有。状态转移0->1：买入-prices[i] 1->0：卖出+prices[i]
     * 确定base case：
     * dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
     * dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i]) = max(dp[i-1][1][1], -prices[i])
     * 解释：k = 0 的 base case，所以 dp[i-1][0][0] = 0。
     * 现在发现 k 都是 1，不会改变，即 k 对状态转移已经没有影响了。
     * 可以进行进一步化简去掉所有 k：
     * dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
     * dp[i][1] = max(dp[i-1][1], -prices[i])
     * 由于新状态只和相邻状态有关系，不需要整个dp数组，只需要一个变量存储相邻的那个状态就可以了，这样可以把空间复杂度降低到O(1)
     *
     * @param prices
     * @return
     */
    // O(n)/O(1)
    public int maxProfit2(int[] prices) {
        int n = prices.length;
        // 状态1：未持有 状态2：持有
        int dp_0 = 0, dp_1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            // 1->0：卖出，受益  0->0：没变动
            // dp[i][0] = Math.max(dp[i-1][1]+prices[i],dp[i-1][0])
            dp_0 = Math.max(dp_1 + prices[i], dp_0);
            // 0->1：买入，减钱，注意这里是0-prices[i]=prices[i]，因为是先买入，再卖出，买入的初始状态dp[i-1][0]=0
            // 0->0：没变动
            // dp[i][1] = Math.max(dp[i-1][1],-prices[i])
            dp_1 = Math.max(dp_1, -prices[i]);
        }
        // 获取最后卖出的结果
        return dp_0;
    }

    /**
     * 121. 买卖股票的最佳时机
     * 方法1：动态规划+状态机
     * 思路：定义一个三维数组dp[n][k][m]，dp：最大的利润，其中n：天数；k：允许交易的最大次数；m：当前持有的状态，分为两种
     * 1表示持有，0表示没有持有。状态转移0->1：买入-prices[i] 1->0：卖出+prices[i]
     * 确定base case：
     * dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
     * dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i]) = max(dp[i-1][1][1], -prices[i])
     * 解释：k = 0 的 base case，所以 dp[i-1][0][0] = 0。【此题的k=1，有1次买入卖出为1次交易】
     * 现在发现 k 都是 1，不会改变，即 k 对状态转移已经没有影响了。
     * 可以进行进一步化简去掉所有 k：
     * dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
     * dp[i][1] = max(dp[i-1][1], -prices[i])
     *
     * @param prices
     * @return
     */
    // O(n)/O(n)
    public int maxProfit(int[] prices) {
        int n = prices.length;
        // dp:最大利润  n:天数 2:表示两种状态 0:不持有 1:持有
        int dp[][] = new int[n][2];
        for (int i = 0; i < n; i++) {
            if (i - 1 == -1) {
                // base case
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }
            // 1->0：卖出，受益  0->0：没变动
            dp[i][0] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][0]);
            // 0->1：买入，减钱，注意这里是0-prices[i]=prices[i]，因为是先买入，再卖出，买入的初始状态dp[i-1][0]=0
            // 0->0：没变动
            dp[i][1] = Math.max(-prices[i], dp[i - 1][1]);
        }
        return dp[n - 1][0];
    }

    /**
     * 867. 转置矩阵
     * https://leetcode.cn/problems/transpose-matrix/description/?show=1
     * 方法：模拟
     * 思路：原矩阵是m行n列，创建一个新的n行m的新矩阵，根据转置规则对新矩阵中的每个元素赋值，则新矩阵为转置后的矩阵
     *
     * @param matrix
     * @return
     */
    // O(m*n)/O(1)
    public int[][] transpose(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] res = new int[n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res[j][i] = matrix[i][j];
            }
        }
        return res;
    }


    /**
     * 1260. 二维网格迁移
     * https://leetcode.cn/problems/shift-2d-grid/description/?show=1
     * 方法：二维转一维数组
     * 思路：假设某元素坐标是a(i,j)，m行n列，转为一维数组的下标index=i*n+j，迁移k次后的坐标为index1=(index+k)%(m*n)，转换为
     * 二维数组坐标(index1/n,index1%n)
     *
     * @param grid
     * @param k
     * @return
     */
    // O(M*N)/O(1)
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                row.add(0);
            }
            res.add(row);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int index1 = (i * n + j + k) % (m * n);
                res.get(index1 / n).set(index1 % n, grid[i][j]);
            }
        }
        return res;
    }

    /**
     * 剑指 Offer 58 - I. 翻转单词顺序
     * https://leetcode.cn/problems/fan-zhuan-dan-ci-shun-xu-lcof/
     * 方法：双指针
     * 思路：反向循环字符串，遇到空格就跳过，接着找到单词的尾部和首部的索引位置，最后将单词存入StringBuilder的变量中
     *
     * @param s
     * @return
     */
    // O(n)/O(1)
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        StringBuilder sbr = new StringBuilder();
        int start, end;
        for (int i = s.length() - 1; i >= 0; i--) {
            // 跳过单词后面的空格
            if (s.charAt(i) == ' ') {
                continue;
            }
            // 找到单词的尾部索引
            end = i;
            // 找到单词的首部索引
            while (i >= 0 && s.charAt(i) != ' ') {
                i--;
            }
            start = i + 1;
            for (int j = start; j <= end; j++) {
                sbr.append(s.charAt(j));
            }
            sbr.append(' ');
        }
        if (sbr.length() > 0) {
            // 删掉最后一个多余的空格
            sbr.deleteCharAt(sbr.length() - 1);
        }
        return sbr.toString();
    }

    /**
     * 剑指 Offer 29. 顺时针打印矩阵
     * https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/
     * 方法：固定边界遍历数组
     *
     * @param matrix
     * @return
     */
    // O(m*n)/O(1)
    public int[] spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }
        int m = matrix.length, n = matrix[0].length;
        int size = m * n;
        int[] res = new int[size];
        int leftBound = 0, rightBound = n - 1;
        int upperBound = 0, downBound = m - 1;
        int index = 0;
        while (index < size) {
            if (upperBound <= downBound) {
                // 在顶部从左侧到右侧遍历
                for (int j = leftBound; j <= rightBound; j++) {
                    res[index++] = matrix[upperBound][j];
                }
                upperBound++;
            }
            if (leftBound <= rightBound) {
                // 在最右侧从上向下遍历
                for (int i = upperBound; i <= downBound; i++) {
                    res[index++] = matrix[i][rightBound];
                }
                rightBound--;
            }
            if (upperBound <= downBound) {
                // 在最底部从右向左遍历
                for (int j = rightBound; j >= leftBound; j--) {
                    res[index++] = matrix[downBound][j];
                }
                downBound--;
            }
            if (leftBound <= rightBound) {
                // 在最左侧从下向上遍历
                for (int i = downBound; i >= upperBound; i--) {
                    res[index++] = matrix[i][leftBound];
                }
                leftBound++;
            }
        }
        return res;
    }

    /**
     * 剑指 Offer II 006. 排序数组中两个数字之和
     * https://leetcode.cn/problems/kLl5u1/
     * 方法2：左右指针
     * 思路：使左右指针相向而行，二者指向的数值之和与target比较
     *
     * @param numbers
     * @param target
     * @return
     */
    // O(N)/O(1)
    public int[] twoSum4(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left, right};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return null;
    }

    /**
     * 剑指 Offer II 006. 排序数组中两个数字之和
     * https://leetcode.cn/problems/kLl5u1/
     * 方法1：二分查找
     * 思路：先固定数组最左侧的一个数a，然后通过二分查找法寻找target-a的值
     *
     * @param numbers
     * @param target
     * @return
     */
    // O(NlogN)/O(1)
    public int[] twoSum3(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            int find = target - numbers[i];
            int left = i + 1, right = numbers.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (numbers[mid] == find) {
                    return new int[]{i, mid};
                } else if (numbers[mid] < find) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return null;
    }

    /**
     * 剑指 Offer 57. 和为s的两个数字
     * https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/
     * 方法2：左右指针
     * 思路：左右指针相向向中间移动，将两个数之和和target比对
     *
     * @param nums
     * @param target
     * @return
     */
    // O(N)/O(1)
    public int[] twoSum2(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                return new int[]{nums[left], nums[right]};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return null;
    }


    /**
     * 剑指 Offer 57. 和为s的两个数字
     * https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/
     * 方法1：二分查找
     * 思路：先固定数组最左边的一个值a，然后通过二分查找寻找target-a的值
     *
     * @param nums
     * @param target
     * @return
     */
    // O(NlogN)/O(1)
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            int left = i + 1, right = nums.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                int find = target - nums[i];
                if (nums[mid] == find) {
                    return new int[]{nums[i], nums[mid]};
                } else if (nums[mid] < find) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return null;
    }


    /**
     * 303. 区域和检索 - 数组不可变
     * https://leetcode-cn.com/problems/range-sum-query-immutable/
     * 方法：前缀和
     * 思路：前n个和作为新数组的第n位置的值
     */
    // O(1)/O(n)
/*    class NumArray {
        int[] preSum;

        // 输入一个数组，构造前缀和
        public NumArray(int[] nums) {
            // preSum[0]=0，便于计算累加和
            preSum = new int[nums.length + 1];
            for (int i = 1; i < preSum.length; i++) {
                preSum[i] = nums[i - 1] + preSum[i - 1];
            }
        }

        // 查询闭区间[left, right] 的累加和=前right项和-前left-1项和
        public int sumRange(int left, int right) {
            return preSum[right + 1] - preSum[left];
        }
    }*/

    /**
     * 283. 移动零
     * https://leetcode-cn.com/problems/move-zeroes/
     * 方法：快慢指针
     * 思路：首先将nums中为0的元素移除，然后将后面所有的元素赋值0
     *
     * @param nums
     */
    // O(n)/O(1)
    public void moveZeroes(int[] nums) {
        // 移除nums中的所有0，返回不含0的数组长度
        int len = removeElement2(nums, 0);
        // 注意这里的len不减1
        for (int i = len; i < nums.length; i++) {
            nums[i] = 0;
        }
    }

    private int removeElement2(int[] nums, int val) {
        int slow = 0, fast = 0;
        while (fast < nums.length) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }

    /**
     * 27. 移除元素
     * https://leetcode-cn.com/problems/remove-element/
     * 方法：双指针(快慢指针)
     * 思路：使用快慢两个指针，快指针在前面走，当指向的值和val不相等就直接，赋值给慢指针指向的值，
     * 然后slow++，也就是计数了一次，最终慢指针的数值就是最终的结果
     *
     * @param nums
     * @param val
     * @return
     */
    // O(n)/O(1)
    public int removeElement(int[] nums, int val) {
        // 如果fast遇到val，直接跳过，否则复制给slow，同时slow前进一步
        int slow = 0, fast = 0;
        while (fast < nums.length) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }

    /**
     * 26. 删除有序数组中的重复项
     * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
     * 方法：双指针(快慢指针)
     *
     * @param nums
     * @return
     */
    // O(N)/O(1)
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int slow = 0, fast = 0;
        while (fast < nums.length) {
            if (nums[slow] != nums[fast]) {
                // 这里需要先++，再赋值，慢指针先指位置再赋值
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        return slow + 1;
    }

    /**
     * 69. x 的平方根
     * 方法一：二分查找
     */
    public static int mySqrt(int x) {
        // 需要有一个单独的变量存储结果
        int left = 0, right = x, result = -1;
        // 等号：0的情况
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            long v = (long) mid * mid; // 精度问题，需要强转
            if (v <= x) {
                left = mid + 1;
                result = mid;
            } else if (v > x) {
                right = mid - 1;
            }
        }
        return result;
    }

    /**
     * 35. 搜索插入位置
     * https://leetcode-cn.com/problems/search-insert-position/
     * 方法：寻找左侧边界的二分查找
     */
    public static int searchInsert(int[] nums, int target) {
        // 注意右下标，左右指针相遇的情况，便找到最终结果
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid;
            }
        }
        return left;
    }

    /**
     * 704. 二分查找
     * https://leetcode-cn.com/problems/binary-search/
     *
     * @param nums
     * @param target
     * @return
     */
    // 时间复杂度：O(logn) 空间复杂度：O(1)
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (target == nums[mid]) {
                return mid;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else if (target > nums[mid]) {
                left = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 344. 反转字符串
     * https://leetcode-cn.com/problems/reverse-string/
     * 方法：双指针
     *
     * @param s
     */
    // 时间复杂度：O(n) 空间复杂度：O(1)
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right++;
        }
    }

    /**
     * 142. 环形链表 II
     * https://leetcode-cn.com/problems/linked-list-cycle-ii/
     * 方法二：双指针(快慢指针)
     *
     * @param head
     * @return
     */
    // 时间复杂度：O(n) 空间复杂度：O(1)
    public static ListNode detectCycle2(ListNode head) {
        if (null == head || null == head.next) {
            return null;
        }
        ListNode fast, slow;
        fast = slow = head;
        // 快指针快走一步
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {// 相遇
                break;
            }
        }
        // 判断没有环的情况
        if (fast == null || fast.next == null) {
            return null;
        }
        slow = head;
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 142. 环形链表 II
     * https://leetcode-cn.com/problems/linked-list-cycle-ii/
     * 方法一：哈希表
     * 思路：使用哈希表，遍历链表的过程中，如果遇到同一个节点，那么表示有环，且是环的起点
     *
     * @param head
     * @return
     */
    // 时间复杂度：O(n) 空间复杂度：O(n)
    public static ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> visited = new HashSet<>();
        while (pos != null) {
            if (visited.contains(pos)) {
                return pos;
            } else {
                visited.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }

    /**
     * 141. 环形链表
     * https://leetcode-cn.com/problems/linked-list-cycle/
     * 方法二：双指针(快慢指针)
     * 用两个指针，一个跑得快，一个跑得慢。如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环；
     * 如果含有环，快指针最终会超慢指针一圈，和慢指针相遇，说明链表含有环
     */
    // 时间复杂度：O(n) 空间复杂度：O(1)
    public static boolean hasCycle2(ListNode head) {
        // 快指针比慢指针快走一步
        ListNode fast, slow;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    /**
     * 141. 环形链表
     * https://leetcode-cn.com/problems/linked-list-cycle/
     * 方法一：哈希表
     * 遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过
     */
    // 时间复杂度：O(n) 空间复杂度：O(n)
    public static boolean hasCycle(ListNode head) {
        Set<ListNode> visitNodes = new HashSet<>();
        while (head != null) {
            if (!visitNodes.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }

    /**
     * 303. 区域和检索 - 数组不可变
     * https://leetcode-cn.com/problems/range-sum-query-immutable/
     * 方法：前缀和
     */
// 时间复杂度：初始化 O(n)O(n)，每次检索 O(1)O(1) 空间复杂度：O(n)O(n)
    class NumArray {

        private int preSum[];// 前缀和数组

        public NumArray(int[] nums) {
            preSum = new int[nums.length + 1];// 第一个元素是0，累加的第一个值
            for (int i = 1; i < preSum.length; i++) {
                // preSum的第i个元素是nums的前i-1个元素之和
                preSum[i] = preSum[i - 1] + nums[i - 1];
            }
        }

        // 查询闭区间的累加和
        public int sumRange(int left, int right) {
            // nums的前right个元素和减去nums的前left-1个元素和
            return preSum[right + 1] - preSum[left];
        }

    }

    /**
     * 9、回文数
     * 解决思路：反转数字比较是否相等
     *
     * @param x
     * @return
     */
    public static boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        int revertNum = 0;
        while (x > revertNum) {
            revertNum = revertNum * 10 + x % 10;
            x = x / 10;
        }
        return x == revertNum || x == revertNum / 10;// 偶数；奇数
    }

    /**
     * 7、整数反转
     * bug：x范围判断的时候需要除以10 result也不能超出精度
     *
     * @param x
     * @return
     */
    public static int reverse(int x) {
        //if (x<-2147483648 || x>2147483647){
        int result = 0;
        while (x != 0) {
            if (result < Integer.MIN_VALUE / 10 || result > Integer.MAX_VALUE / 10) {
                return 0;
            }
            int yu = x % 10;
            x /= 10;
            result = result * 10 + yu;
        }
        return result;
    }

    /**
     * 1、计算两数之和
     * 时间复杂度O(n^2)
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoNum(int[] nums, int target) {
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int sum = nums[i] + nums[j];
                if (sum == target) {
                    result[0] = i;
                    result[1] = j;
                    break;
                }
            }
        }
        return result;
    }

    /**
     * 官方好方法
     * 使用hash表 时间复杂度O(n)
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoNum2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);//题目中：你可以假设每种输入只会对应一个答案。即数组中没有重复元素
        }
        return new int[0];
    }
}
